import javafx.util.Pair;

import java.util.*;

/**
* @description: 面试题 17.09. 第 k 个数
* @author hewei
* @date 2022/9/28 14:42
* @version 1.0
*/

public class GetKthMagicNumber {

    public int getKthMagicNumber1(int k) {
        PriorityQueue<Pair<Long, Long>> heap = new PriorityQueue<>(Comparator.comparingLong(a -> (long) a.getKey() * a.getValue()));
        if (k == 1) return 1;
        heap.add(new Pair<>(1L, 3L));
        long ans = 0L;
        while (--k > 0) {
            Pair<Long, Long> poll = heap.poll();
            Long key = poll.getKey();
            Long value = poll.getValue();
            List<Pair<Long, Long>> list = new ArrayList<>();
            list.add(poll);
            while (!heap.isEmpty() && (heap.peek().getKey() * heap.peek().getValue() == value * key)) {
                Pair<Long, Long> pair = heap.poll();
                list.add(pair);
            }
            ans = value * key;
            heap.add(new Pair<>(ans, 3l));
            for (Pair<Long, Long> pair : list) {
                Long value1 = pair.getValue();
                Long key1 = pair.getKey();
                if (value1 < 6) {
                    if (value1 > 3) {
                        heap.add(new Pair<>(key1, 7l));
                    } else {
                        heap.add(new Pair<>(key1, 5l));
                    }
                }
            }
        }
        return Math.toIntExact(ans);
    }

    public int getKthMagicNumber(int k) {
        int p1 = 0;
        int p2 = 0;
        int p3 = 0;
        long[] nums = new long[k];
        nums[0] = 1L;
        for (int i = 1; i < k; i++) {
            long min = Math.min(3 * nums[p1], Math.min(5 * nums[p2], 7 * nums[p3]));
            if (min == 3 * nums[p1]) ++p1;
            if (min == 5 * nums[p2]) ++p2;
            if (min == 7 * nums[p3]) ++p3;
            nums[i] = min;
        }
        return (int) nums[k - 1];
    }
}
